Test Series - Data Structure

3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

Test Number 99/115

Q: Which of the following variant of a hash table has the best cache performance?
A. hash table using a linked list for separate chaining
B. hash table using binary search tree for separate chaining
C. hash table using open addressing
D. hash table using a doubly linked list for separate chaining
Solution: Implementation of the hash table using open addressing has a better cache performance as compared to separate chaining. It is because open addressing stores data in the same table without using any extra space.
Q: What is the advantage of hashing with chaining?
A. cache performance is good
B. uses less space
C. less sensitive to hash function
D. has a time complexity of O(n) in the worst case
Solution: Hashing with separate chaining has an advantage that it is less sensitive to a hash function. It is also easy to implement.
Q: What is the disadvantage of hashing with chaining?
A. not easy to implement
B. takes more space
C. quite sensitive to hash function
D. table gets filled up easily
Solution: Hashing with separate chaining has a disadvantage that it takes more space. This space is used for storing elements in case of a collision.
Q: What is the time complexity of insert function in a hash table using a binary tree?
A. O(1)
B. O(n)
C. O(log n)
D. O(n log n)
Solution: Time complexity of insert function in a hash table is O(1) on an average. Condition is that the number of collisions should be low.
Q: What is the time complexity of the search function in a hash table using a binary tree?
A. O(1)
B. O(n)
C. O(log n)
D. O(n log n)
Solution: Time complexity of search function in a hash table is O(1). Condition is that the number of collisions should be low.
Q: What is the time complexity of the delete function in the hash table using a binary tree?
A. O(1)
B. O(n)
C. O(log n)
D. O(n log n)
Solution: Time complexity of delete function in a hash table is O(1). Condition is that the hash function should be such that the number of collisions should be low.
Q: What is the advantage of a hash table over BST?
A. hash table has a better average time complexity for performing insert, delete and search operations
B. hash table requires less space
C. range query is easy with hash table
D. easier to implement
Solution: Hash table and BST both are examples of data structures. Hash table has an advantage that it has a better time complexity for performing insert, delete and search operations.
Q: What is the disadvantage of BST over the hash table?
A. BST is easier to implement
B. BST can get the keys sorted by just performing inorder traversal
C. BST can perform range query easily
D. Time complexity of hash table in inserting, searching and deleting is less than that of BST
Solution: BST has an advantage that it is easier to implement, can get the keys sorted by just performing in-order traversal and can perform range query easily. Hash table has lesser time complexity for performing insert, delete and search operations.
Q: Which of the following technique stores data separately in case of a collision?
A. Open addressing
B. Double hashing
C. Quadratic probing
D. Chaining using a binary tree
Solution: Open addressing is used to store data in the table itself in case of a collision. Whereas chaining stores data in a separate entity.
Q: In open addressing the hash table can never become full.
A. True
B. False
C. none
D. ....
Solution: There are two methods of handling collisions in a hash table:- open addressing and separate chaining. In open addressing the hash table can become full.

You Have Score    /10